解題程式碼

var findMinHeightTrees = function (n, edges) {
  if (n === 1) return [0]; // 處理 n = 1、edges = []

  const graph = new Map();
  const indegrees = new Array(n).fill(0);
  const queue = [];

  for (const [e, v] of edges) {
    graph.has(v) ? graph.get(v).push(e) : graph.set(v, [e]);
    graph.has(e) ? graph.get(e).push(v) : graph.set(e, [v]);

    indegrees[e]++;
    indegrees[v]++;
  }

  for (let i = 0; i < n; i++) {
    if (indegrees[i] === 1) queue.push(i);
  }

  while (n > 2) {
    const size = queue.length;
    n -= size;

    for (let i = 0; i < size; i++) {
      const node = queue.shift();

      for (const neighbor of graph.get(node)) {
        if (--indegrees[neighbor] === 1) queue.push(neighbor);
      }
    }
  }

  return queue;
};

解題思路、演算法

這題考拓撲排序，首先建立一個 hashMap，將各節點和它相連的所有節點記錄到 hashMap 中。

圖建立好後，從葉節點開始走訪，一層層刪除 degree 為 1 的節點，直到整個 Tree 剩下 1 or 2 個節點，就為最終結果。

剝洋蔥...

為什麼可以這樣一層層剝去節點找到最小高度的 trees，因為找到圖某段路線的中間節點，再把中間節點當作 root，就可以找到最小高度的 trees

ex: 有個 graph 為 1 => 2 => 3 <= 4 <= 5，則 3 為中間節點，又有個 graph 為 1 => 2 => <= 4 <= 5，則 2, 4 為中間節點

解法的時間、空間複雜度

時間複雜度: O(V)，V = n，節點數
空間複雜度: O(V + 2E) = O(V)，儲存所有節點，然後 A 節點到 B 節點的 edge，還有相反的方向

參考資料

Minimum Height Trees - Leetcode 310 - Python

✅[C++/Python] 3 Simple Solution w/ Explanation | Brute-Force + 2x DFS + Remove Leaves w/ BFS

✔️ Solution - III (Remove Leaves using BFS) 有圖解